gcd最大公约数

本节目标：理解“gcd最大公约数”的核心思路，并能把它用于实际开发或面试表达。 在Python中，gcd函数用于计算两个数的最大公约数（Greatest Common Divisor）。最大公约数是能同时整除两个数的最大正整数。gcd函数是数学和算法中的一个基本概念，它在处理分数、解决一些数学问题和算法优化中非常有用。

在Python 3.5及以上版本中，gcd函数可以直接通过math模块调用： import math

计算12和16的最大公约数

result = math.gcd(12, 16) print(result) # 输出4

在上面的埃及分数分解问题中，gcd函数的作用是约简分数。给定分子a和分母b，通过计算它们的最大公约数，并分别除以这个最大公约数，可以得到一个等价的最简分数。这是因为分子和分母都除以它们的最大公约数后，新的分子和分母之间不再有除1以外的公约数，因此分数达到了最简形式。

例如，假设在某一步中，我们得到了分数6/8。6和8的最大公约数是2，所以我们可以把6/8约简为(6÷2)/(8÷2) = 3/4。使用gcd函数可以自动化这个过程，保证分解过程中的每个分数都是最简的。

def gcd(a, b): """计算最大公约数（GCD）""" while b: a, b = b, a % b return a

欧几里得算法的原理

欧几里得算法基于一个关键的原理：两个正整数a和b（假设a \> b）的最大公约数与b和a % b（a除以b的余数）的最大公约数相同。换句话说，如果你不断地用较小的数去除较大的数，然后用余数再去除前一个除数，重复这个过程，直到余数为0，那么最后的除数就是这两个数的最大公约数。

gcd函数的工作过程

1. 初始化：函数开始时接受两个参数a和b，不需要它们有特定的大小顺序，因为算法会在第一步处理中自动调整它们的位置。

2. 循环：函数内部使用while循环，循环的条件是b不等于0。在循环体内，算法执行两个操作：

• 交换：将b的值赋给a，这相当于保留了当前的除数作为下一轮的被除数。
• 计算余数：计算a除以b的余数，并将这个余数赋给b。这个步骤实现了上述的核心原理，即使用较小的数去除较大的数，并用余数继续这个过程。

3. 返回结果：当b变为0时，循环结束，此时a的值就是a和b的最大公约数，函数返回这个值。

示例

如果a = 48和b = 18，那么算法的执行过程如下：

1. 第一次循环：a = 18, b = 48 % 18 = 12
2. 第二次循环：a = 12, b = 18 % 12 = 6
3. 第三次循环：a = 6, b = 12 % 6 = 0

循环结束，此时a = 6，所以48和18的最大公约数是6。

欧几里得算法之所以有效，是因为它将问题规模迅速缩小，直到找到最大公约数为止。这种方法对于大数也非常高效，是计算两个数最大公约数的标准方法。